package toOffer;

import java.util.HashMap;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/30 17:12
 * @description <p>排序的循环链表</p>
 */
public class toOffer4_5_29 {
    public static void main(String[] args) {
        int insertVal = 2;

        Node node1 = new Node(3);
        Node node2 = new Node(4);
        node1.next = node2;
        Node node3 = new Node(1);
        node2.next = node3;
        node3.next = node1;

        Node node = insert(node1, insertVal);
        int count = 4;
        while (count > 0) {
            System.out.print(node.val + " ");
            node = node.next;
            count--;
        }
    }

    /**
     *
     * @param head
     * @param insertVal
     * @return
     */
    public static Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        //head为null的情况
        if (head == null){
            node.next = node;
            return node;
        }else if (head.next == head){
            //只有一个节点，且head指向自己
            head.next = node;
            node.next = head;
        }else {
            //节点数量大于2
            head = fun(head, node);
        }
        return head;
    }

    /**
     * 把node节点插入head节点所在的链表
     * 有三种情况：
     * （1）node节点的值小于head链表的最小值，那么就把这个节点插入到最大值和最小值之间
     * （2）node节点的值位大于最小值、小于最大值，直接插就行
     * （3）node节点的值大于最大值，把这个节点插入到最大值和最小值之间
     * @param head
     * @param node
     * @return
     */
    public static Node fun(Node head, Node node){
        Node bigNode = head;
        Node next = head.next;
        //遍历head链表，找到最大节点
        while (next != head){
            if (next.val > bigNode.val){
                bigNode = next;
            }
            if (next.val <= node.val && node.val <= next.next.val){
                node.next = next.next;
                next.next = node;
                return head;
            }
            next = next.next;
        }
        if (next.val > node.val || node.val > next.next.val){
            node.next = bigNode.next;
            bigNode.next = node;
        }
        return head;
    }

    private static class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }
}
